package main

import "fmt"

type MonotonicQueue struct {
	maxQueue []int
}

func Constructor(lenth int) MonotonicQueue {
	return MonotonicQueue{
		maxQueue: make([]int, 0, lenth),
	}
}

func (m *MonotonicQueue) Max() (max int, ok bool) {
	if len(m.maxQueue) == 0 {
		ok = false
		return
	}
	max = m.maxQueue[0]
	ok = true
	return
}

func (m *MonotonicQueue) Push(n int) {
	for {
		if len(m.maxQueue) > 0 && m.maxQueue[len(m.maxQueue)-1] < n {
			m.maxQueue = append(m.maxQueue[:len(m.maxQueue)-1], m.maxQueue[len(m.maxQueue):]...)
		} else {
			break
		}
	}
	m.maxQueue = append(m.maxQueue, n)
}

func (m *MonotonicQueue) Pop(n int) {
	if m.maxQueue[0] == n {
		m.maxQueue = m.maxQueue[1:len(m.maxQueue)]
	}
}

func main() {
	t := Constructor(1)
	fmt.Println(t)
	t.Push(1)
	fmt.Println(t)
	t.Push(2)
	fmt.Println(t)
	t.Push(3)
	fmt.Println(t)
	t.Push(3)
	fmt.Println(t)
	t.Push(2)
	fmt.Println(t)
	t.Push(3)
	fmt.Println(t)
	t.Push(4)
	fmt.Println(t)
	t.Push(2)
	t.Pop(2)
	fmt.Println(t)
	fmt.Println(t.Max())

}
